import java.util.ArrayList;
import java.util.LinkedList;

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int n = candidates.length;
        List<List<Integer>> res = new ArrayList<>();
        if (n == 0) {
            return res;
        }

        LinkedList<Integer> path = new LinkedList<>();
        backTrace(candidates, 0, target, path, res);
        return res;
    }

    // 枚举哪个
    private void backTrace(int[] candidates, int start, int target, LinkedList<Integer> path, List<List<Integer>> res) {
        if (target == 0)
            res.add(new ArrayList<>(path));
        if (target <= 0) return;
        
        // 从start开始搜索，避免上个元素出现在之后的path中，造成可置换的情况导致重复
        // 即：从每一层的第 2 个结点开始，都不能再搜索产生同一层结点已经使用过的 candidate 里的元素。
        for (int i = start; i < candidates.length; i++){
            path.add(candidates[i]);
            // 由于每个元素可以重复使用，下一轮搜索的起点依然是i
            backTrace(candidates, i, target-candidates[i], path, res);
            path.removeLast();
        }
    }


    // 选或不选
    private void backTrace2(int[] candidates, int i, int target, LinkedList<Integer> path, List<List<Integer>> res) {
        if (i == candidates.length)
            return;
        if (target == 0){
            res.add(new ArrayList<>(path));
            return;
        }
        if (target <= 0) return;
        
        backTrace2(candidates, i+1, target, path, res);

        // 从start开始搜索，避免上个元素出现在之后的path中，造成可置换的情况导致重复
        // 即：从每一层的第 2 个结点开始，都不能再搜索产生同一层结点已经使用过的 candidate 里的元素。
        if ( target - candidates[i] >= 0 ){
            path.add(candidates[i]);
            // 由于每个元素可以重复使用，下一轮搜索的起点依然是i
            backTrace(candidates, i, target - candidates[i], path, res);
            path.removeLast();
        }
    }
}